The present invention is directed to circuitry for performing a fast-Fourier-transform operation. It is directed particularly to butterfly circuits used in such operations.
Digital signal processing has advanced to a state in which discrete Fourier transformations of data sampled at frequencies on the order of megahertz can be performed in real time. In any case in which the number of samples in each transformation is at all large, the so-called fast Fourier transform is used.
The fast Fourier transform is is an algorithm that is based on the fact that a discrete Fourier transformation can be generated by combining, in a relatively simple manner, Fourier transformations of subsets of the input record. Each of these subset transformations, in turn, can be generated from even smaller subsets. Typically, the input-data record is ultimately divided into subrecords of only two or four data points on which two- or four-point discrete Fourier transforms are performed. The results of these operations are multiplied by so-called twiddle factors--i.e., complex numbers equal to exponentials of purely imaginary arguments--and then subjected to further two-or four-point Fourier transformations.
There is no reason in theory why the individual transformations have to be two-point or four-point operations, but these are the most popular because the multiplications in two- or four-point Fourier transformations are all operations in which one of the factors is plus or minus unity or plus or minus the square root of minus one; in other words, no multiplication circuit is needed for the individual transformations in two- or four-point transforms, although multiplication circuits are necessary for twiddle-factor multiplications.
In a circuit for implementing a fast Fourier transformation, a hardware device for performing the basic two- or four-point Fourier transformation and multiplying by twiddle factors is used repeatedly. It is referred to as a butterfly circuit. If it performs a two-point transformation, the circuit is referred to as a radix-two butterfly circuit, whereas a butterfly circuit that performs a four-point transformation is referred to as a radix-four butterfly circuit.
The choice of which type of butterfly circuit to use depends on a number of factors, including the speed required and the number of sample points in each transformation. In general, any reasonably long transformation that can be performed in a radix-four circuit requires fewer multiplications in a radix-four circuit than it does in a radix-two circuit, so the radix-four circuit is in some sense more efficient. However, the radix-four circuit requires more hardware and is thus more expensive. Furthermore, a system that performs only radix-four butterfly operations can transform only an input record whose number of samples is 4.sup.K, where K is a positive integer. A radix-two butterfly circuit, on the other hand, requires less hardware and can operate on any sample whose length is 2.sup.K.
In selecting hardware for multi-purpose fast Fourier transformation, therefore, one must first decide which type of butterfly circuit to use. If the required speed and efficiency are low enough, use of a radix-two butterfly circuit is desirable in light of its lower cost and the greater versatility in selection of input-record lengths. In a multi-purpose environment, however, it is not always possible to predict the speed that will be needed, and the user may soon find that he needs to purchase a radix-four butterfly circuit in addition to his radix-two butterfly circuit.
On the other hand, purchasing a radix-four butterfly circuit right away saves the cost of a radix-two butterfly circuit if the efficiency afforded by a radix-four circuit proves to be necessary. However, if more versatility in the selection of record length is needed than is afforded with a radix-four system, a radix-two butterfly circuit will additionally need to be used with the radix-four butterfly circuit to achieve the radix-four speed for radix-two record lengths. At present, therefore, many multi-purpose transformation devices end up with both radix-two hardware and radix-four hardware.
Moreover, there is often an additional requirement for a complex-to-real processor if, as is typically the case, the input data are purely real. Purely real input data can be applied to both the real and the imaginary input ports of the system so that the capacity of the FFT circuit is not wasted. If they are, however, the complex-to-real hardware is needed to adjust for the fact that real data are applied to the imaginary ports.
An object of the present invention is thus to reduce the hardware requirements of fast-Fourier-transform circuits.